package com.example.binarytree;


import java.util.LinkedList;

/**二叉树数据结构
 * Created by 3020mt on 2016/3/17.
 */
public class BinaryTree <T> {
    private TreeNode rootNode;
    public BinaryTree(T [] target){
        rootNode = creatTree(0,target);
    }
    /**
     * 生成二叉树,根据数组按照完全二叉树的形式生成,数组值为空表示树节点为空
     * @param targets
     */
    public TreeNode creatTree(int start,T [] target){
        if(target.length==0){
            return null;
        }
        TreeNode root = new TreeNode(target[start]);
        if(start * 2 +1 <target.length && target[start*2 +1]!=null){
            root.setLeftChildNode(creatTree((start*2+1),target));
        }
        if(start*2+2<target.length && target[start *2 +2]!=null){
            root.setRightChildNode(creatTree(start*2+2,target));
        }
        return root;
    }

    /**
     * 树节点类
     * @param <T>
     */
    public class TreeNode<T>{
        private T target;
        private TreeNode leftChildNode;
        private TreeNode rightChildNode;
        public TreeNode(T target){
            this.target = target;
        }

        public T getTarget() {
            return target;
        }

        public void setTarget(T target) {
            this.target = target;
        }

        public TreeNode getLeftChildNode() {
            return leftChildNode;
        }

        public void setLeftChildNode(TreeNode leftChildNode) {
            this.leftChildNode = leftChildNode;
        }

        public TreeNode getRightChildNode() {
            return rightChildNode;
        }

        public void setRightChildNode(TreeNode rightChildNode) {
            this.rightChildNode = rightChildNode;
        }
    }

    /**
     * 层级遍历树
     * @param root
     */
    public void readTree(TreeNode root){
        LinkedList<TreeNode> treeA = new LinkedList<>();
        treeA.add(root);
        while(!treeA.isEmpty()){
            TreeNode removeLast = treeA.removeLast();
            //Todo: 操作元素
            // 层级遍历树查找B在A中对应的子树根节点
            if (removeLast.getLeftChildNode() != null)
                treeA.addFirst(removeLast.getLeftChildNode());

            if (removeLast.getRightChildNode() != null)
                treeA.addFirst(removeLast.getRightChildNode());
        }
    }
}
